package com.zhangx.datastructure.sort;

/**
 * @ClassName Sort
 * @Description 排序算法
 * @Author zhangx
 * @Date 2021/2/2 9:38
 **/
public class Sort {

    int count = 0;

    /**
     * 冒泡排序-简化版，最简单但是性能最低，只能算是个比较吧
     * @param l
     */
    void bubleSort0(SqList l){
        for (int i = 1; i < l.length; i++) {
            for (int j = i + 1; j < l.length; j++) {
                count++;
                if (l.r[i]>l.r[j]){
                    l.swap(l,i,j);
                }
            }
        }
        System.out.println("比较了"+count+"次");
    }

    /**
     * 正规冒泡 O(n^2)
     * @param l
     */
    void bubleSort(SqList l){
        for (int i = 1; i < l.length; i++) {
            for (int j = l.length-1; j >= i; j--) {
                count++;
                if (l.r[j]>l.r[j+1]){
                    l.swap(l,j,j+1);
                }
            }
        }
        System.out.println("比较了"+count+"次");
    }

    /**
     * 改进冒泡，如果数组本身比较有序，可以改进
     * 减少无意义的比较
     * @param l
     */
    void bubleSort2(SqList l){
        boolean flag = true;
        for (int i = 1; i < l.length && flag; i++) {
            flag = false;
            for (int j = l.length-1; j >= i; j--) {
                count++;
                if (l.r[j]>l.r[j+1]){
                    l.swap(l,j,j+1);
//                    只有发生了交换才是true
                    flag = true;
                }
            }
        }
        System.out.println("比较了"+count+"次");
    }

    /**
     * 选择排序
     * 就是每次交换，都把最值交换到前面，O(n^2)，虽然跟冒泡一样，但是交换少，优于冒泡
     */
    void selectSort(SqList l){
        for (int i = 1; i < l.length; i++) {
            int min = i;
            for (int j = i+1; j <=l.length ; j++) {
                if (l.r[min]>l.r[j]){
                    min = j;
                }
            }
            if (i!=min){
                l.swap(l,i,min);
            }
        }
    }

    /**
     * 插入排序 也是O(n^2)，但是比冒泡和选择稍好一些
     * @param l
     */
    void insertSort(SqList l){
        int j = 0;
        for (int i = 2; i <= l.length; i++) {
            if (l.r[i]<l.r[i-1]){//前面的比后面的大
//                把r[0]当做哨兵
                l.r[0] = l.r[i];//把后面的小值当做哨兵
                for (j = i-1; l.r[j]>l.r[0] ; j--) {//插入=后移
                    l.r[j+1] = l.r[j];
                }
                l.r[j+1] = l.r[0];//最前面的换成哨兵
            }
        }
    }

    /**
     * 希尔排序
     * @param l
     */
    void shellSort(SqList l){
        int increment = l.length;
        int j = 0;
        do{
            increment = increment/3 + 1;//增量序列
            for (int i = increment + 1; i <=l.length ; i++) {
                if (l.r[i] < l.r[i-increment]){
//                    将 l.r[i]插入有序增量子表
                    l.r[0] = l.r[i];//暂存
                    for (j = i - increment; j > 0 && l.r[0]<l.r[j]; j-=increment) {
                        l.r[j+increment] = l.r[j];//后移
                    }
                    l.r[j+increment] = l.r[0];//暂存值插入
                }
            }
        }while (increment > 1);
    }


    /**
     * 堆排序 O(nlogn)
     * 适合数据量多，不是很稳定
     * 大逻辑
     * @param l
     */
    void heapSort(SqList l){
//        把l 中的 r 构建成一个大顶堆
        for (int i = l.length/2; i >0 ; i--) {//只调节双亲节点就够了
            heapAdjust(l,i,l.length);
        }
        for (int i = l.length; i > 1; i--) {
            l.swap(l,1,i);//将堆顶与未经排序的序列最后一个元素交换
            heapAdjust(l,1,i-1);//将r[1..i-1]重新调整为大顶堆
        }
    }

    /**
     * 堆排序的核心
     * 已知在 r[s..m]中 除 s 外[s+1,...,m]满足堆排序
     * 本函数调整r[s]，使r[s,....,m]称为大顶堆
     * @param l
     * @param s
     * @param m
     */
    private void heapAdjust(SqList l, int s, int m) {
        int temp = l.r[s];
        for (int j = 2*s; j <= m ; j*=2) {// 沿关键字较大孩子节点向下筛选
//            s 的左孩子一定是2s,右孩子一定是2s+1
            if (j<m && (l.r[j]<l.r[j+1])){//左孩子<右孩子
                ++j;//j 为关键字中较大记录下标-变为右孩子
            }
            //否则还是左孩子
            if (temp >= l.r[j]){
                break;// rc 插入到s上
            }
            l.r[s] = l.r[j];
            s = j;
        }
        l.r[s] = temp;//插入
    }

    /**
     * 归并排序-bug
     * 递归方式
     * @param l
     */
    public void mergeSort(SqList l){
        mSort(l.r,l.r,1,l.length);
    }

    /**
     * 归并排序-非递归
     * @param l
     */
    public void mergeSort2(SqList l){
        int[] tr = new int[l.length];
        int k = 1;
        while (k <l.length){
            mergePass(l.r,tr,k,l.length);
            k = 2*k; // 子序列长度加倍
            mergePass(tr,l.r,k,l.length);
            k = 2*k; // 子序列长度加倍
        }
    }

    private void mergePass(int[] sr, int[] tr, int s, int n) {
        int i = 1;
        int j;
        while (i <= n - 2*s + 1){//如果长度是奇数个，最后那个会剩下
            merge(sr,tr,i,i+s-1,i+2*s-1);//两两归并
            i = i+2*s;
        }
        if (i < n - s + 1){//归并最后两个
            merge(sr,tr,i,i+s-1,n);
        }else {
            for ( j = i; j <= n ; j++) {
                tr[j] = sr[j];
            }
        }
    }


    /**
     * 将sr[s..t]归并排序为tr1[s...t]
     * @param sr
     * @param tr1
     * @param s
     * @param t
     */
    private void mSort(int[] sr,int[] tr1,int s,int t){
        int m = 0;
        int[] tr2 = new int[11];
        if (s == t){
            tr1[s] = sr[s];
        }else {
            m = (s+t)/2;//将sr[s..t]分为sr[s..m]和sr[m+1...t]
//            不断的分解
            mSort(sr,tr2,s,m);//递归将sr[s...m]归并为tr2[s...]
            mSort(sr,tr2,m+1,t);//递归将sr[m+1..t]归并为tr2[m+1..t]
            merge(tr2,tr1,s,m,t);//将tr2[s..m]和tr2[m+1...t]归并到tr1[s..t]
        }
    }

    /**
     * 将sr[i..m]和sr[m+1,n]合并到tr
     * sr的左右两部分已经是内部有序的
     * @param sr
     * @param tr
     * @param i
     * @param m
     * @param n
     */
    private void merge(int[] sr, int[] tr, int i, int m, int n) {
        int j, k, l = 0;
//        将sr 中记录归并到tr 从小到大
//        这里是将左右两半的最小值依次比较，最小的放入tr
//        见解释P411
        for (j = m + l, k = i; i <= m && j <= n; k++) {//k用于sr 的下标
            if (sr[i] < sr[j]) {
                tr[k] = sr[i++];
            } else {
                tr[k] = sr[j++];
            }
        }
        if (i <= m) {
            for (l = 0; l <= m - i; l++)
                tr[k + l] = sr[i + l];        /* 将剩余的SR[i..m]复制到TR */
        }
        if (j <= n) {
            for (l = 0; l <= n - j; l++)
                tr[k + l] = sr[j + l];        /* 将剩余的SR[j..n]复制到TR */

        }
    }

    /**
     * O(nlogn)
     * 空间复杂度O(logn)
     * @param l
     */
    public void quickSort(SqList l){
        qSort(l,1,l.length);
    }

    /**
     * 对子序列Low...high快排
     * @param l
     * @param low
     * @param high
     */
    private void qSort(SqList l, int low, int high) {
        int pivot;//枢轴值，左边比他小，右边比大大
        if (low < high){
            pivot = partition(l,low,high);// 将l[low...high]一分为二

            qSort(l,low,pivot-1);//低子表
            qSort(l,pivot+1,high);//高子表
        }
//        对于大数据使用快排
//        low-high<MAX_LEN_INSERT_SORT的使用插入，插入是简单排序中最快的，适用于小数组
    }

    /**
     * 不使用递归了，优化，因为不平很的数组递归栈深度=n，耗费性能
     * ？？
     * @param l
     * @param low
     * @param high
     */
    private void qSort1(SqList l, int low, int high) {
        int pivot;//枢轴值，左边比他小，右边比大大
        while (low < high){//从if 变为while
            pivot = partition1(l,low,high);// 将l[low...high]一分为二

            qSort1(l,low,pivot-1);//低子表
            low = pivot + 1;//尾递归，这里不一样，少了一次递归--等价--qSort(l,pivot+1,high)
        }
    }

    /**
     * 快排的核心
     * @param l
     * @param low
     * @param high
     * @return
     */
    private int partition(SqList l, int low, int high) {
        int pivotkey;
//        ----------------三数取中优化---------------------------
        int m = low + (high - low)/2;//计算第一个数的下标-中间值
        if (l.r[low] > l.r[high]){
            l.swap(l,low,high);//左右交换
        }
        if (l.r[m]>l.r[high]){
            l.swap(l,high,m);
        }
        if (l.r[m]<l.r[low]){
            l.swap(l,m,low);
        }
//        还有9数取中，就是这个方法搞三次，得到三个中中数，三个中数再来一次得到中数，相当于计算4次
//        -------------------------------------------
        pivotkey = l.r[low];//用字表中第一个作为枢轴记录，如果是中间值最好，否则就是斜树了
        while (low < high){//从两端向中间扫描
            while (low < high && l.r[high]>=pivotkey){
                high--;
            }
            l.swap(l,low,high);//比枢轴小的交换到低端
            while (low < high && l.r[low]<=pivotkey){
                low++;
            }
            l.swap(l,high,low);
        }
        return low;
    }

    /**
     * 快排优化
     * @param l
     * @param low
     * @param high
     * @return
     */
    private int partition1(SqList l, int low, int high) {
        int pivotkey;
        //        ----------------三数取中优化---------------------------
        int m = low + (high - low)/2;//计算第一个数的下标-中间值
        if (l.r[low] > l.r[high]){
            l.swap(l,low,high);//左右交换
        }
        if (l.r[m]>l.r[high]){
            l.swap(l,high,m);
        }
        if (l.r[m]<l.r[low]){
            l.swap(l,m,low);
        }
//        -------------------------------------------
        pivotkey = l.r[low];//用字表中第一个作为枢轴记录，如果是中间值最好，否则就是斜树了
        l.r[0] = pivotkey;//将枢轴值备份到0
        while (low < high){
            while (low < high && l.r[high] >= pivotkey){
                high--;
            }
            l.r[low] = l.r[high];//替换而不是交换
            while (low < high && l.r[low]<=pivotkey){
                low++;
            }
            l.r[high] = l.r[low];//替换而不是交换
        }
        l.r[low] = l.r[0];//将枢轴值替换回来
        return low;
    }

    public static void main(String[] args) {

        Sort sort = new Sort();

        SqList l = new SqList();
        l.r[1] = 9;
        l.r[2] = 1;
        l.r[3] = 5;
        l.r[4] = 8;
        l.r[5] = 3;
        l.r[6] = 7;
        l.r[7] = 4;
        l.r[8] = 6;
        l.r[9] = 2;
//        l.r[10] = -1;



//        l.length = 10;
//        sort.bubleSort0(l);

//        l.length = 9;
//        sort.bubleSort(l);
//        l.length = 9;
//        l = new SqList();
//        l.r[1] = 2;
//        l.r[2] = 1;
//        l.r[3] = 3;
//        l.r[4] = 4;
//        l.r[5] = 5;
//        l.r[6] = 6;
//        l.r[7] = 7;
//        l.r[8] = 8;
//        l.r[9] = 9;
//        sort.bubleSort2(l);
//        System.out.println(l);


        l = new SqList();
        l.r[1] = 9;
        l.r[2] = 1;
        l.r[3] = 5;
        l.r[4] = 8;
        l.r[5] = 3;
        l.r[6] = 7;
        l.r[7] = 4;
        l.r[8] = 6;
        l.r[9] = 2;
        l.length = 9;
//        sort.selectSort(l);

//        l = new SqList();
//        l.r[1] = 5;
//        l.r[2] = 3;
//        l.r[3] = 4;
//        l.r[4] = 6;
//        l.r[5] = 2;
//        l.length = 5;
//        sort.insertSort(l);//首位是哨兵没用
//        System.out.println(l);

//        l = new SqList();
//        l.r[1] = 9;
//        l.r[2] = 1;
//        l.r[3] = 5;
//        l.r[4] = 8;
//        l.r[5] = 3;
//        l.r[6] = 7;
//        l.r[7] = 4;
//        l.r[8] = 6;
//        l.r[9] = 2;
//        l.length = 9;
//        sort.shellSort(l);//首位是哨兵没用
//        System.out.println(l);

//        l = new SqList();
//        l.r[0] = 0;
//        l.r[1] = 50;
//        l.r[2] = 10;
//        l.r[3] = 90;
//        l.r[4] = 30;
//        l.r[5] = 70;
//        l.r[6] = 40;
//        l.r[7] = 80;
//        l.r[8] = 60;
//        l.r[9] = 20;
//        l.length = 9;
//        sort.heapSort(l);
//        System.out.println(l);

        l = new SqList();
        l.r[0] = 0;
        l.r[1] = 50;
        l.r[2] = 10;
        l.r[3] = 90;
        l.r[4] = 30;
        l.r[5] = 70;
        l.r[6] = 40;
        l.r[7] = 80;
        l.r[8] = 60;
        l.r[9] = 20;
        l.length = 9;
//            sort.mergeSort(l);
//        sort.mergeSort2(l);
//        System.out.println(l);

        l = new SqList();
        l.r[0] = 0;
        l.r[1] = 50;
        l.r[2] = 10;
        l.r[3] = 90;
        l.r[4] = 30;
        l.r[5] = 70;
        l.r[6] = 40;
        l.r[7] = 80;
        l.r[8] = 60;
        l.r[9] = 20;
        l.length = 9;
        sort.quickSort(l);
        System.out.println(l);
    }
}
